package io.github.hadyang.leetcode.offer;

import org.junit.Test;

/** @author haoyang.shi */
public class MoreThanHalfNum {

  @Test
  public void test() {
    System.out.println(MoreThanHalfNum_Solution(new int[] {1, 2, 3, 2, 2, 2, 5, 4, 2}));
    System.out.println(MoreThanHalfNum_Solution(new int[] {}));
    System.out.println(MoreThanHalfNum_Solution(new int[] {1}));
    System.out.println(MoreThanHalfNum_Solution(new int[] {1, 2}));
  }

  public int MoreThanHalfNum_Solution(int[] array) {

    int start = 0, end = array.length - 1;
    int mid = array.length / 2;

    int index = partition(array, start, end);
    if (index == mid) {
      return array[index];
    }

    while (index != mid && start <= end) {
      if (index > mid) {
        end = index - 1;
        index = partition(array, start, end);
      } else {
        start = index + 1;
        index = partition(array, start, end);
      }
    }

    if (checkIsHalf(array, index)) return array[index];

    return 0;
  }

  private boolean checkIsHalf(int[] array, int index) {
    if (index < 0) {
      return false;
    }

    int count = 0;
    for (int i : array) {
      if (array[index] == i) {
        count++;
      }
    }

    return count > array.length / 2;
  }

  private int partition(int[] array, int start, int end) {
    if (start >= array.length || start < 0 || end >= array.length || end < 0) {
      return -1;
    }

    int key = array[start];
    int left = start, right = end;

    while (left < right) {
      while (left < right && array[right] >= key) {
        right--;
      }
      if (left < right) {
        array[left] = array[right];
        left++;
      }

      while (left < right && array[left] <= key) {
        left++;
      }
      if (left < right) {
        array[right] = array[left];
        right--;
      }
    }
    array[left] = key;

    return left;
  }
}
